package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:删除二叉搜索树中的节点
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）
 * 的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * User:Mr.Du
 * Date:2023/9/14
 * Time:00:10
 */
public class DeleteNode {
    /**
     * 有以下两种情况：
     * 1、没找到删除的节点，
     * 1.1、遍历到空节点直接返回
     *
     * 2、找到删除的节点
     * 2.1、左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
     * 2.2、删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
     * 2.3、删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
     * 2.4、左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，
     *      返回删除节点右孩子为新的根节点。
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val < key){
            root.right = deleteNode(root.right, key);
        }else if(root.val > key) {
            root.left = deleteNode(root.left, key);
        } else{
            // 下面两个if包含了2.1-2.3
            if(root.left == null) return root.right;
            if(root.right == null) return root.left;
            TreeNode node = root.right;
            while(node.left != null) node = node.left;
            node.left = root.left;
            return root.right;
        }
        return root;
    }
}
